lib/Mi manual de algoritmos/version_actual/manual.tex

   1 \documentclass[10pt,letterpaper,twocolumn,twosided]{article}
   2 %\documentclass[10pt,letterpaper]{article}
   3 % ---------------------------------------------------------------
   4 \usepackage[utf8]{inputenc}
   5 \usepackage[spanish]{babel}
   6 \usepackage{listings}
   7 \usepackage[usenames,dvipsnames]{color}
   8 \usepackage{amsmath}
   9 \usepackage{verbatim}
  10 \usepackage{hyperref}
  11 \usepackage{color}
  12 \usepackage{geometry}
  13 %Poner la página en landscape
  14 \geometry{verbose,landscape,letterpaper,tmargin=2cm,bmargin=2cm,lmargin=2cm,rmargin=2cm}
  15
  16 \newcommand{\codigofuente}[1]{
  17 \verbatiminput{#1}
  18 \dotfill
  19 }
  20 \setlength{\columnsep}{0.25in}
  21 \setlength{\columnseprule}{1px}
  22
  23 % ---------------------------------------------------------------
  24 \begin{document}
  25 % ---------------------------------------------------------------
  26 \title{Resumen de algoritmos para torneos de programación}
  27 \author{Andrés Mejía}
  28 \date{\today}
  29 \maketitle
  30 % ---------------------------------------------------------------
  31
  32 % ---------------------------------------------------------------
  33 \tableofcontents
  34 % \lstlistoflistings
  35 \lstloadlanguages{C++}
  36 % ---------------------------------------------------------------
  37 \section{Plantilla}
  38 \codigofuente{./src/template.cpp}
  39 % ---------------------------------------------------------------
  40 \section{Teoría de números}
  41 % ---------------------------------------------------------------
  42 \subsection{Big mod}
  43 %\input{./src/number_theory/bigmod}%.tex
  44 \codigofuente{./src/number_theory/bigmod.cpp}
  45
  46 \subsection{Criba de Eratóstenes}
  47 \small
  48 \textbf{Field-testing:}
  49 \begin{itemize}
  50 \item \emph{SPOJ} -  2912 - Super Primes
  51 \item \emph{Live Archive} - 3639 - Prime Path
  52 \end{itemize}
  53
  54 \normalsize
  55 Marca los números primos en un arreglo. Algunos tiempos de ejecución:
  56 \begin{center}
  57   \begin{tabular}{c c}
  58     \hline\hline
  59     SIZE & Tiempo (s) \\ [0.5ex]
  60     \hline
  61     100000 & 0.003 \\
  62     1000000 & 0.060 \\
  63     10000000 & 0.620 \\
  64     100000000 & 7.650 \\ [1ex]
  65     \hline
  66   \end{tabular}
  67 \end{center}
  68 \codigofuente{./src/number_theory/criba.cpp}
  69
  70 \subsection{Divisores de un número}
  71 Imprime todos los divisores de un número (en desorden) en O($\sqrt{n}$).
  72 Hasta 4294967295 (máximo \textit{unsigned int}) responde instantáneamente. Se puede
  73 forzar un poco más usando \textit{unsigned long long} pero más allá de $10^{12}$ empieza a
  74 responder muy lento.
  75 \codigofuente{./src/number_theory/divisores.cpp}
  76
  77 \section{Combinatoria}
  78 \subsection{Cuadro resumen}
  79 Fórmulas para combinaciones y permutaciones:
  80 \begin{center}
  81   \renewcommand{\arraystretch}{2} %Multiplica la altura de cada fila de la tabla por 2
  82   % Si quiero aumentar el tamaño de una fila en particular insertar \rule{0cm}{1cm} en esa fila.
  83   \begin{tabular}{| c | c | c |}
  84     \hline
  85     \textit{Tipo} & \textit{¿Se permite la repetición?} & \textit{Fórmula} \\ [1.5ex]
  86     \hline\hline
  87
  88     $r$-permutaciones & No & $ \displaystyle\frac{n!}{(n-r)!} $ \\ [1.5ex]
  89     \hline
  90     $r$-combinaciones & No & $ \displaystyle\frac{n!}{r!(n-r)!} $ \\  [1.5ex]
  91     \hline
  92     $r$-permutaciones & Sí & $ \displaystyle n^{r} $ \\
  93     \hline
  94     $r$-combinaciones & Sí & $ \displaystyle\frac{(n+r-1)!}{r!(n-1)!} $ \\ [1.5ex]
  95     \hline
  96   \end{tabular}
  97   \renewcommand{\arraystretch}{1}
  98 \end{center}
  99 Tomado de \textit{Matemática discreta y sus aplicaciones}, Kenneth Rosen, 5${}^{\hbox{ta}}$ edición, McGraw-Hill, página 315.
 100
 101 \subsection{Combinaciones, coeficientes binomiales, triángulo de Pascal}
 102 \emph{Complejidad:} $ O(n^2) $ \\
 103 $$ {n \choose k} = \left\{
 104   \begin{array}{c l}
 105     1 & k = 0\\
 106     1 & n = k\\
 107     \displaystyle {n - 1 \choose k - 1} + {n - 1 \choose k} & \mbox{en otro caso}\\
 108   \end{array}
 109 \right.
 110 $$
 111
 112 \codigofuente{./src/combinatoria/pascal_triangle.cpp}
 113
 114 \bigskip
 115 \textbf{Nota:} $ \displaystyle {n \choose k }  $ está indefinido en el código anterior si $ n > k$. ¡La tabla puede estar llena con cualquier basura del compilador!
 116
 117 \subsection{Permutaciones con elementos indistinguibles}
 118 El número de permutaciones \underline{diferentes} de $n$ objetos, donde hay $n_{1}$ objetos indistinguibles de tipo 1,
 119 $n_{2}$ objetos indistinguibles de tipo 2, ..., y $n_{k}$ objetos indistinguibles de tipo $k$, es
 120 $$
 121 \frac{n!}{n_{1}!n_{2}! \cdots n_{k}!}
 122 $$
 123 \textbf{Ejemplo:} Con las letras de la palabra \texttt{PROGRAMAR} se pueden formar $ \displaystyle \frac{9!}{2! \cdot 3!} =
 124 30240 $ permutaciones \underline{diferentes}.
 125 \subsection{Desordenes, desarreglos o permutaciones completas}
 126
 127 Un desarreglo es una permutación donde ningún elemento $i$ está en la
 128 posición $i$-ésima. Por ejemplo, \textit{4213} es un desarreglo de 4 elementos pero
 129 \textit{3241} no lo es porque el 2 aparece en la posición 2.
 130
 131 Sea $D_{n}$ el número de desarreglos de $n$ elementos, entonces:
 132 $$ {D_{n}} = \left\{
 133   \begin{array}{c l}
 134     1 & n = 0\\
 135     0 & n = 1\\
 136     (n-1)(D_{n-1} + D_{n-2}) & n \geq 2\\
 137   \end{array}
 138 \right.
 139 $$
 140 Usando el principio de inclusión-exclusión, también se puede encontrar la fórmula
 141 $$
 142 D_{n} = n!\left [ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^{n}\frac{1}{n!} \right ]
 143 = n! \sum_{i=0}^{n} \frac{(-1)^{i}}{i!}
 144 $$
 145
 146 \section{Grafos}
 147 \subsection{Algoritmo de Dijkstra}
 148 El peso de todas las aristas debe ser no negativo.
 149 \\
 150 \codigofuente{./src/grafos/dijkstra.cpp}
 151
 152 \subsection{Minimum spanning tree: Algoritmo de Prim}
 153
 154 \codigofuente{./src/grafos/prim.cpp}
 155
 156 \subsection{Minimum spanning tree: Algoritmo de Kruskal + Union-Find}
 157 \codigofuente{./src/grafos/kruskal.cpp}
 158
 159 \subsection{Algoritmo de Floyd-Warshall}
 160 \codigofuente{./src/grafos/floyd.cpp}
 161
 162 \subsection{Algoritmo de Bellman-Ford}
 163 Si no hay ciclos de coste negativo, encuentra la distancia más corta
 164 entre un nodo y todos los demás. Si sí hay, permite saberlo. \\ El
 165 coste de las aristas \underline{sí} puede ser negativo
 166 (\emph{Debería}, si no es así se puede usar Dijsktra o Floyd).
 167 \codigofuente{./src/grafos/bellman.cpp}
 168
 169 \subsection{Puntos de articulación}
 170 \codigofuente{./src/grafos/puntos_articulacion.cpp}
 171
 172 \subsection{Máximo flujo: Método de Ford-Fulkerson, algoritmo de Edmonds-Karp}
 173 El algoritmo de Edmonds-Karp es una modificación al método de Ford-Fulkerson. Este último
 174 utiliza DFS para hallar un camino de aumentación, pero la sugerencia de Edmonds-Karp
 175 es utilizar BFS que lo hace más eficiente en algunos grafos.
 176 \medskip
 177
 178 \codigofuente{./src/grafos/ford_fulkerson.cpp}
 179
 180 \subsection{Máximo flujo para grafos dispersos usando Ford-Fulkerson}
 181
 182 \small
 183 \textbf{Field-testing:}
 184 \begin{itemize}
 185 \item \emph{UVa} - 563 - Crimewave
 186 \end{itemize}
 187 \normalsize
 188
 189 \codigofuente{./src/grafos/ford_fulkerson_sparse.cpp}
 190
 191 \subsection{Componentes fuertemente conexas: Algoritmo de Tarjan}
 192 \label{tarjan}
 193 \codigofuente{./src/grafos/tarjan.cpp}
 194
 195 \subsection{2-Satisfiability}
 196 Dada una ecuación lógica de conjunciones de disyunciones de 2 términos, se pretente decidir si existen valores de verdad que puedan asignarse a las variables para hacer cierta la ecuación. \\
 197 Por ejemplo, $(b_1 \vee \neg b_2) \wedge (b_2 \vee b_3) \wedge (\neg b_1 \vee \neg b_2) $ es verdadero cuando $b_1$ y $b_3$ son verdaderos y $b_2$ es falso. \\
 198 \textbf{Solución:} Se sabe que $(p \rightarrow q) \leftrightarrow (\neg p \vee q)$. Entonces se traduce cada disyunción en una implicación y se crea un grafo donde los nodos son cada variable y su negación. Cada implicación es una arista en este grafo. Existe solución si nunca se cumple que una variable y su negación están en la misma componenete fuertemente conexa (Se usa el algoritmo de Tarjan, \ref{tarjan}).
 199
 200 \section{Programación dinámica}
 201 \subsection{Longest common subsequence}
 202 \codigofuente{./src/dp/lcs.cpp}
 203 \subsection{Partición de troncos}
 204 Este problema es similar al problema de \textit{Matrix Chain Multiplication}. Se tiene
 205 un tronco de longitud $n$, y $m$ puntos de corte en el tronco. Se puede hacer un corte a la vez,
 206 cuyo costo es igual a la longitud del tronco. ¿Cuál es el mínimo costo para partir todo el tronco
 207 en pedacitos individuales?
 208 \\
 209 \medskip
 210 \textbf{Ejemplo:} Se tiene un tronco de longitud 10. Los puntos de corte son 2, 4, y 7. El mínimo
 211 costo para partirlo es 20, y se obtiene así:
 212 \begin{itemize}
 213 \item Partir el tronco (0, 10) por 4. Vale 10 y quedan los troncos (0, 4) y (4, 10).
 214 \item Partir el tronco (0, 4) por 2. Vale 4 y quedan los troncos (0, 2), (2, 4) y (4, 10).
 215 \item No hay que partir el tronco (0, 2).
 216 \item No hay que partir el tronco (2, 4).
 217 \item Partir el tronco (4, 10) por 7. Vale 6 y quedan los troncos (4, 7) y (7, 10).
 218 \item No hay que partir el tronco (4, 7).
 219 \item No hay que partir el tronco (7, 10).
 220 \item El costo total es $10+4+6 = 20$.
 221 \end{itemize}
 222
 223 \medskip
 224 El algoritmo es $O(n^3)$, pero optimizable a $O(n^2)$ con una tabla adicional:
 225 \codigofuente{./src/dp/particion_troncos.cpp}
 226
 227 \section{Strings}
 228 \subsection{Algoritmo de Knuth-Morris-Pratt (KMP)}
 229
 230 Computa el arreglo $border$ que contiene la longitud del borde más largo de todos
 231 los prefijos de una cadena. \\
 232 Un borde de una cadena es otra cadena más corta que es a la vez prefijo y sufijo de la original
 233 (por ejemplo, \textit{aba} es un border de \textit{abacaba} porque es más corta que \textit{abacaba}
 234 y es al mismo tiempo prefijo y sufijo de \textit{abacaba}. \textit{ab} también es un borde de \textit{abacaba}.
 235 \textit{abac} no es un borde de \textit{abacaba} porque no es un sufijo). \\
 236
 237 En el código, \verb_border[i]_ contiene el borde más grande del prefijo de longitud $i$ de $needle$ ($needle$
 238 es el patrón que se quiere buscar en la otra cadena). Una ejemplo del arreglo \verb_border_ es: \\
 239
 240
 241 \begin{center}
 242   \begin{tabular}{| c | c c c c c c c c c c c c c c c | }
 243     \hline
 244     i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ [0.5ex]
 245     \hline
 246     \hline
 247     \textit{needle} & a & b & a & c & a & b & a & c & a & b & a & d & a & b & \\
 248     \textit{border} & -1 & 0 & 0 & 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 0 & 1 & 2 \\
 249     \hline
 250   \end{tabular}
 251 \end{center}
 252
 253
 254
 255 \codigofuente{./src/strings/kmp.cpp}
 256
 257 \subsection{Algoritmo de Aho-Corasick}
 258 Sirve para buscar muchos patrones en una cadena. Por ejemplo,
 259 dada la cadena $ahishers$ y los patrones $\{he, she, hers, his\}$,
 260 encuentra que $his$ aparece en la posición 1, $he$ aparece en la posición 4,
 261 $she$ aparece en la posición 3 y $hers$ aparece en la posición 4. \\
 262
 263 Complejidad: $O(n + m)$ donde $n$ es la longitud de la cadena en la que hay que buscar
 264 y $m$ es la suma de las longitudes de todos los patrones. \\
 265
 266 \codigofuente{./src/strings/aho-corasick.cpp}
 267 \subsection{Suffix arrays y longest common prefix}
 268 \codigofuente{./src/strings/suffix_arrays.cpp}
 269
 270 \section{Geometría}
 271
 272 \subsection{Identidades trigonométricas}
 273
 274 $$ \sin(\alpha \pm \beta) = \sin \alpha \cos \beta \pm \cos \alpha \sin \beta $$
 275 $$ \cos(\alpha \pm \beta) = \cos \alpha \cos \beta \mp \sin \alpha \sin \beta $$
 276 $$ \tan(\alpha \pm \beta) = \frac{\tan \alpha \pm \tan \beta}{1 \mp \tan \alpha \tan \beta} $$
 277
 278
 279 \subsection{Área de un polígono}
 280 Si P es un polígono simple (no se intersecta a sí mismo) su área está dada por: \\
 281
 282 $ A(P) = \frac{1}{2} \displaystyle\sum_{i=0}^{n-1} (x_{i} \cdot y_{i+1} - x_{i+1} \cdot y_{i}) $ \\
 283 \bigskip
 284 \codigofuente{./src/geometria/polygon_area.cpp}
 285
 286 \subsection{Centro de masa de un polígono}
 287 Si P es un polígono simple (no se intersecta a sí mismo) su centro de masa está dado por: \\
 288
 289 $ \displaystyle\bar{C}_{x} = \frac{ \displaystyle\iint_{R} x \, dA }{M} = \frac{1}{6M}\sum_{i=1}^{n} (y_{i+1} - y_{i}) (x_{i+1}^2 + x_{i+1} \cdot x_{i} + x_{i}^2) $
 290
 291 \medskip
 292
 293 $\displaystyle\bar{C}_{y} = \frac{ \displaystyle\iint_{R} y \, dA }{M} = \frac{1}{6M} \sum_{i=1}^{n} (x_{i} - x_{i+1}) (y_{i+1}^2 + y_{i+1} \cdot y_{i} + y_{i}^2)$
 294
 295 \medskip
 296
 297 Donde $ M $ es el área del polígono. \\
 298
 299 Otra posible fórmula equivalente:
 300
 301 $ \displaystyle\bar{C}_{x} = \frac{1}{6A} \sum_{i=0}^{n-1} (x_{i} + x_{i+1}) (x_{i} \cdot y_{i+1} - x_{i+1} \cdot y_{i}) $
 302
 303 \medskip
 304
 305 $ \displaystyle\bar{C}_{y} = \frac{1}{6A} \sum_{i=0}^{n-1} (y_{i} + y_{i+1}) (x_{i} \cdot y_{i+1} - x_{i+1} \cdot y_{i}) $
 306
 307
 308 \subsection{Convex hull: Graham Scan}
 309 \emph{Complejidad:} $ O(n \log_{2}{n}) $
 310 \codigofuente{./src/geometria/grahamscan.cpp}
 311
 312 \subsection{Convex hull: Andrew's monotone chain}
 313 \emph{Complejidad:} $ O(n \log_{2}{n}) $
 314 \codigofuente{./src/geometria/monotonechain.cpp}
 315
 316 \subsection{Mínima distancia entre un punto y un segmento}
 317 \codigofuente{./src/geometria/distance_point_to_segment.cpp}
 318
 319 \subsection{Mínima distancia entre un punto y una recta}
 320 \codigofuente{./src/geometria/distance_point_to_line.cpp}
 321
 322 \subsection{Determinar si un polígono es convexo}
 323 \codigofuente{./src/geometria/is_convex_polygon.cpp}
 324
 325 \subsection{Determinar si un punto está dentro de un polígono convexo}
 326 \codigofuente{./src/geometria/is_inside_convex_polygon.cpp}
 327
 328 \subsection{Determinar si un punto está dentro de un polígono cualquiera}
 329 \small
 330 \textbf{Field-testing:}
 331 \begin{itemize}
 332 \item \emph{TopCoder} -  SRM 187 - Division 2 Hard - PointInPolygon
 333 \item \emph{UVa} - 11665 - Chinese Ink
 334 \end{itemize}
 335 \normalsize
 336 \codigofuente{./src/geometria/is_inside_concave_polygon.cpp}
 337
 338 \subsection{Hallar la intersección de dos rectas}
 339 \codigofuente{./src/geometria/line_line_intersection.cpp}
 340
 341 \subsection{Hallar la intersección de dos segmentos de recta}
 342 \label{hallar_interseccion_segmentos}
 343 \small
 344 \textbf{Field-testing:}
 345 \begin{itemize}
 346 \item \emph{UVa} - 11665 - Chinese Ink
 347 \end{itemize}
 348 \normalsize
 349
 350 \codigofuente{./src/geometria/segment_segment_intersection.cpp}
 351
 352 \subsection{Determinar si dos segmentos de recta se intersectan o no}
 353
 354 Si sólo se necesita determinar si dos segmentos se intersectan, pero no hallar
 355 el punto de intersección, se puede usar este código que es más corto que \ref{hallar_interseccion_segmentos}.
 356 La función \verb!point_in_box! es la misma que en \ref{hallar_interseccion_segmentos}.
 357
 358 \codigofuente{./src/geometria/check_segment_intersection.cpp}
 359
 360 \subsection{Centro del círculo que pasa por 3 puntos}
 361 \small
 362 \textbf{Field-testing:}
 363 \begin{itemize}
 364 \item \emph{Live Archive} - 4807 - Cocircular Points
 365 \end{itemize}
 366 \normalsize
 367
 368 \codigofuente{./src/geometria/circle_through_3_points.cpp}
 369
 370 % ---------------------------------------------------------------
 371 \section{Estructuras de datos}
 372 \subsection{Árboles de Fenwick ó Binary indexed trees}
 373
 374 Se tiene un arreglo $\{a_0, a_1, \cdots, a_{n-1}\}$. Los árboles
 375 de Fenwick permiten encontrar $ \displaystyle \sum_{k=i}^{j} a_k $ en orden $O(\log_{2}{n})$ para parejas de $(i, j)$ con $i \leq j$. De la misma manera, permiten sumarle una cantidad a un $a_i$ también en tiempo $O(log_{2}{n})$.
 376 \medskip
 377 \codigofuente{./src/estructuras/fenwick.cpp}
 378
 379 \subsection{Segment tree}
 380 \codigofuente{./src/estructuras/segment_tree.cpp}
 381
 382 % ---------------------------------------------------------------
 383 \section{Misceláneo}
 384 \subsection{El \textit{parser} más rápido del mundo}
 385 \begin{itemize}
 386 \item Cada no-terminal: un método
 387 \item Cada lado derecho:
 388   \begin{itemize}
 389   \item invocar los métodos de los no-terminales o
 390   \item Cada terminal: invocar proceso \textit{match}
 391   \end{itemize}
 392 \item Alternativas en una producción: se hace un \textit{if}
 393 \end{itemize}
 394 \medskip
 395 No funciona con gramáticas recursivas por izquierda ó en las que en algún momento haya
 396 varias posibles escogencias que empiezan por el mismo caracter (En ambos casos la gramática se puede factorizar).
 397
 398 \medskip
 399 \textbf{Ejemplo:} Para la gramática:
 400 $$
 401 A \longrightarrow (A)A
 402 $$ $$
 403 A \longrightarrow \epsilon
 404 $$
 405
 406 \codigofuente{./src/misc/parser_recursivo_desc.cpp}
 407
 408 \subsection{Checklist para corregir un Wrong Answer}
 409 Consideraciones que podrían ser causa de un Wrong Answer:
 410 \begin{itemize}
 411   \begin{item}
 412     Overflow.
 413   \end{item}
 414
 415   \begin{item}
 416     El programa termina anticipadamente por la condición en el ciclo de lectura.
 417     Por ejemplo, se tiene \verb_while (cin >> n >> k && n && k)_ y un caso válido de entrada
 418     es n = 1 y k = 0.
 419   \end{item}
 420
 421   \begin{item}
 422     El grafo no es conexo.
 423   \end{item}
 424
 425   \begin{item}
 426     Puede haber varias aristas entre el mismo par de nodos.
 427   \end{item}
 428
 429   \begin{item}
 430     Las aristas pueden tener costos negativos.
 431   \end{item}
 432
 433   \begin{item}
 434     El grafo tiene un sólo nodo.
 435   \end{item}
 436
 437   \begin{item}
 438     La cadena puede ser vacía.
 439   \end{item}
 440
 441   \begin{item}
 442     Las líneas pueden tener espacios en blanco al principio o al final (Cuidado al usar \texttt{getline} o \texttt{fgets}).
 443   \end{item}
 444
 445   \begin{item}
 446     El arreglo no se limpia entre caso y caso.
 447   \end{item}
 448
 449   \begin{item}
 450     Estás imprimiendo una línea en blanco con un espacio (\verb_printf(" \n")_ en vez de \verb_printf("\n")_  ó \verb_puts(" ")_  en vez de \verb_puts("")_).
 451   \end{item}
 452
 453   \begin{item}
 454     Hay pérdida de precisión al leer variables como \verb_double_ y converterirlas a enteros. Por ejemplo, en C++, \verb_floor(0.29 * 100) == 28_.
 455   \end{item}
 456
 457   \begin{item}
 458     La rana se puede quedar quieta.
 459   \end{item}
 460
 461   \begin{item}
 462     El producto cruz está invertido. Realmente es $\mid<a_x, a_y> \times <b_x, b_y>\mid = a_x \mathbf{b_y} - a_y \mathbf{b_x} \neq a_x \mathbf{b_x} - a_y \mathbf{b_y} $.
 463   \end{item}
 464 \end{itemize}
 465
 466 \subsection{Redondeo de dobles}
 467
 468 Para redondear un doble a $k$ cifras, usar:
 469
 470 $$ \frac{\lfloor 10^{k} \cdot x + 0.5 \rfloor }{10^k} $$
 471
 472 Ejemplo:
 473
 474 \begin{verbatim}
 475   double d = 1.2345;
 476   d = floor(1000 * d + 0.5) / 1000;
 477 \end{verbatim}
 478
 479 Al final, \verb_d_ es 1.235.
 480
 481 \subsubsection{Convertir un doble al entero más cercano}
 482
 483 \begin{center}
 484   \renewcommand{\arraystretch}{1.3} %Multiplica la altura de cada fila de la tabla por 2
 485   % Si quiero aumentar el tamaño de una fila en particular insertar \rule{0cm}{1cm} en esa fila.
 486   \begin{tabular}{| c | c | c | }
 487     \hline
 488     \textit{Código} & \textit{Valores originales ($d$)} & \textit{Nuevos valores ($k$)} \\
 489     \hline\hline
 490
 491     \verb_int k = floor(d + 0.5 + EPS);_ & 0.0  & 0 \\ \cline{2-3}
 492     (con \verb_EPS = 1e-9_)              & 0.1  & 0 \\ \cline{2-3}
 493                                          & 0.5  & 1 \\ \cline{2-3}
 494                                          & 0.4999999999999999 & 1 \\ \cline{2-3}
 495                                          & \verb_cos(1e-7) * 0.5_ =  & \\ & 0.4999999999999975 & 1 \\ \cline{2-3}
 496                                          & 0.9  & 1 \\ \cline{2-3}
 497                                          & 1.0 & 1 \\ \cline{2-3}
 498                                          & 1.4 & 1 \\ \cline{2-3}
 499                                          & 1.5 & 2 \\ \cline{2-3}
 500                                          & 1.6 & 2 \\ \cline{2-3}
 501                                          & 1.9 & 2 \\ \cline{2-3}
 502                                          & 2.0 & 2 \\ \cline{2-3}
 503                                          & 2.1 & 2 \\ \cline{2-3}
 504                                          & -0.0  & 0 \\ \cline{2-3}
 505                                          & -0.1  & 0 \\ \cline{2-3}
 506                                          & -0.5  & 0 \\ \cline{2-3}
 507                                          & -0.4999999999999999 & 0 \\ \cline{2-3}
 508                                          & \verb_-cos(1e-7) * 0.5_ =  & \\ & -0.4999999999999975 & 0 \\ \cline{2-3}
 509                                          & -0.9  & -1 \\ \cline{2-3}
 510                                          & -1.0 & -1 \\ \cline{2-3}
 511                                          & -1.4 & -1 \\ \cline{2-3}
 512                                          & -1.5 & -1 \\ \cline{2-3}
 513                                          & -1.6 & -2 \\ \cline{2-3}
 514                                          & -1.9 & -2 \\ \cline{2-3}
 515                                          & -2.0 & -2 \\ \cline{2-3}
 516                                          & -2.1 & -2 \\ \cline{2-3}
 517     \hline
 518   \end{tabular}
 519   \renewcommand{\arraystretch}{1}
 520 \end{center}
 521
 522 \begin{center}
 523   \renewcommand{\arraystretch}{1.3} %Multiplica la altura de cada fila de la tabla por 2
 524   % Si quiero aumentar el tamaño de una fila en particular insertar \rule{0cm}{1cm} en esa fila.
 525   \begin{tabular}{| c | c | c | }
 526     \hline
 527     \textit{Código} & \textit{Valores originales ($d$)} & \textit{Nuevos valores ($k$)} \\
 528     \hline\hline
 529
 530     \verb_int k = floor(d + 0.5);_       & 0.0  & 0 \\ \cline{2-3}
 531                                          & 0.1  & 0 \\ \cline{2-3}
 532                                          & 0.5  & 1 \\ \cline{2-3}
 533                                          & 0.4999999999999999 & 0 \\ \cline{2-3}
 534                                          & \verb_cos(1e-7) * 0.5_ =  & \\ & 0.4999999999999975 & 0 \\ \cline{2-3}
 535                                          & 0.9  & 1 \\ \cline{2-3}
 536                                          & 1.0 & 1 \\ \cline{2-3}
 537                                          & 1.4 & 1 \\ \cline{2-3}
 538                                          & 1.5 & 2 \\ \cline{2-3}
 539                                          & 1.6 & 2 \\ \cline{2-3}
 540                                          & 1.9 & 2 \\ \cline{2-3}
 541                                          & 2.0 & 2 \\ \cline{2-3}
 542                                          & 2.1 & 2 \\ \cline{2-3}
 543                                          & -0.0  & 0 \\ \cline{2-3}
 544                                          & -0.1  & 0 \\ \cline{2-3}
 545                                          & -0.5  & 0 \\ \cline{2-3}
 546                                          & -0.4999999999999999 & 0 \\ \cline{2-3}
 547                                          & \verb_-cos(1e-7) * 0.5_ =  & \\ & -0.4999999999999975 & 0 \\ \cline{2-3}
 548                                          & -0.9  & -1 \\ \cline{2-3}
 549                                          & -1.0 & -1 \\ \cline{2-3}
 550                                          & -1.4 & -1 \\ \cline{2-3}
 551                                          & -1.5 & -1 \\ \cline{2-3}
 552                                          & -1.6 & -2 \\ \cline{2-3}
 553                                          & -1.9 & -2 \\ \cline{2-3}
 554                                          & -2.0 & -2 \\ \cline{2-3}
 555                                          & -2.1 & -2 \\ \cline{2-3}
 556     \hline
 557   \end{tabular}
 558   \renewcommand{\arraystretch}{1}
 559 \end{center}
 560
 561 \subsubsection{Redondear un doble a cierto número de cifras de precisión}
 562
 563
 564 \section{Java}
 565 \subsection{Entrada desde entrada estándar}
 566 Este primer método es muy fácil pero es mucho más ineficiente porque utiliza Scanner en vez de BufferedReader:
 567 \codigofuente{./src/java/io_estandar_easy.java}
 568
 569 \bigskip
 570
 571 Este segundo es más rápido:
 572 \codigofuente{./src/java/io_estandar.java}
 573 \subsection{Entrada desde archivo}
 574 \codigofuente{./src/java/io_file.java}
 575
 576 \subsection{Mapas y sets}
 577 Programa de ejemplo:
 578 \codigofuente{./src/java/maps_sets.java} \\
 579 La salida de este programa es: \\
 580 \bigskip
 581 \ttfamily
 582 \fbox{\parbox{2.0in}{
 583     Maps\\
 584     m.size() = 1\\
 585     465\\
 586     null\\
 587     \\
 588     Sets\\
 589     54 presente.\\
 590     s.size() = 3\\
 591     54\\
 592     3576\\
 593     1000000007\\
 594     s.size() = 0\\
 595   }
 596 }
 597 \\ \normalfont\normalsize
 598 \bigskip
 599
 600 Si quiere usarse una clase propia como llave del mapa o como elemento del set, la clase debe implementar
 601 algunos métodos especiales: Si va a usarse un TreeMap ó TreeSet hay que implementar los métodos \texttt{compareTo} y
 602 \texttt{equals} de la interfaz \texttt{Comparable} como en la sección \ref{colas_de_prioridad_java}. Si va a usarse
 603 un HashMap ó HashSet hay más complicaciones.\\
 604 \smallskip
 605 \textbf{Sugerencia:} Inventar una manera de codificar y decodificar la clase en una String o un Integer y meter esa representación en el mapa o set: esas clases ya tienen los métodos implementados.
 606
 607 \subsection{Colas de prioridad}
 608 \label{colas_de_prioridad_java}
 609 Hay que implementar unos métodos. Veamos un ejemplo: \\
 610 \codigofuente{./src/java/priority_queue.java}\\
 611 La salida de este programa es: \\
 612
 613 \ttfamily
 614 \fbox{\parbox{2.0in}{
 615     peso = 0, destino = 12\\
 616     peso = 0, destino = 8\\
 617     peso = 0, destino = 13\\
 618     peso = 3, destino = 7\\
 619     peso = 1876, destino = 4\\
 620   }
 621 }
 622  \normalfont\normalsize
 623
 624 Vemos que la función de comparación que definimos no tiene en cuenta \texttt{destino},
 625 por eso no desempata cuando dos \texttt{Items} tienen el mismo \texttt{peso} si no que escoge
 626 cualquiera de manera arbitraria.
 627
 628 \section{C++}
 629 \subsection{Entrada desde archivo}
 630 \codigofuente{./src/c++/io_file.cpp}
 631
 632 \subsection{Strings con caractéres especiales}
 633 \codigofuente{./src/c++/unicode.cpp}
 634
 635 \emph{Nota}: Como alternativa a la función getline, se pueden utilizar las funciones fgetws y fputws, y más adelante swscanf y wprintf:
 636 \codigofuente{./src/c++/fgetws.cpp}
 637
 638 \subsection{Imprimir un doble con \texttt{cout} con cierto número de cifras de precisión}
 639 Tener cuidado con números negativos, porque el comportamiento es diferente.
 640
 641 \codigofuente{./src/c++/cout_con_precision.cpp}
 642
 643 \end{document}